﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MachineLearning
{
     /// <summary>
    /// This class is used to classify data using KNN, however the nearest neighbors are based
    /// on an aggregate ranking for the distance between each element of a data point. Each element
    /// of the input data is ranked according to how close it is to any incoming data that needs
    /// to be classified. This ranking is then aggregated and the highest ranking data points are
    /// used to classify the incoming sample.
    /// </summary>
    public class RankKNN
    {

        private List<object[]> _data;
        private int[] _labels;
        private List<Func<object, object, double>> _distances;
        private Func<double[], double> _aggregator;

        /// <summary>
        /// The original indexes of the the sorted data
        /// </summary>
        private List<int[]> _originalIndexes;

        /// <summary>
        /// Storage for the rankings of our data compared to an incoming data point
        /// </summary>
        private int[,] _rankings;

        /// <summary>
        /// The distance between each data point
        /// </summary>
        private List<double[]> _deltas;

        /// <summary>
        /// Constructor for RankKNN class
        /// </summary>
        /// <param name="data">The list of object arrays that hold the data</param>
        /// <param name="labels">The array of labels for each data point</param>
        /// <param name="distanceFunctions">The list of functions to calculate distance between this data and data to be classified</param>
        /// <param name="aggregator">A function to aggregate rankings for each datapoint. If null, a simple average is used</param>
        public RankKNN(List<object[]> data, int[] labels, List<Func<object, object, double>> distances, Func<double[], double> aggregator)
        {
            _data = data;
            _labels = labels;
            _distances = distances;
            _aggregator = aggregator;
            _originalIndexes = new List<int[]>();
            _deltas = new List<double[]>();
            // Sort all the data
            foreach (var column in _data)
            {
                int[] permidx = Enumerable.Range(0, column.Length).ToArray();
                Array.Sort(column, permidx);
                _originalIndexes.Add(permidx);
            }

            // Find out the deltas in the sorted data
            for (int i = 0; i < _data.Count; i++)
            {
                var column = _data[i];
                double[] d = new double[column.Length];
                d[0] = 0.0;
                for (int j = 1; j < column.Length; j++)
                {
                    d[j] = _distances[i](column[j], column[j - 1]);
                }
                _deltas.Add(d);
            }

            // Storage for our rankings
            _rankings = new int[_data.Count, _labels.Length];
        }
        
        /// <summary>
        /// Merges n sorted arrays and associated indexes into a single sorted array
        /// </summary>
        private void MergeSorted(List<double[]> arrays, List<int[]> indexes, out double[] mergedArray, out int[] mergedIndex)
        {
            var arrayTops = new List<int>();
            int length = 0;
            foreach(var array in arrays)
            {
                length += array.Length;
                arrayTops.Add(0);
            }
            mergedArray = new double[length];
            mergedIndex = new int[length];

            int k = 0;
            while (k < mergedArray.Length)
            {
                // Find the minimum of all the current array tops
                double minTop = Double.MaxValue;
                int minIdx = -1;
                for (int i = 0; i < arrays.Count; i++)
                {
                    var array = arrays[i];
                    if (arrayTops[i] < array.Length)
                    {
                        if (array[arrayTops[i]] < minTop)
                        {
                            minTop = array[arrayTops[i]];
                            minIdx = i;
                        }
                    }
                }
                var marray = arrays[minIdx];
                var mindex = indexes[minIdx];
                mergedArray[k] = marray[arrayTops[minIdx]];
                mergedIndex[k] = mindex[arrayTops[minIdx]];
                arrayTops[minIdx]++;
                k++;
            }
        }

        /// <summary>
        /// Accumulates an array, i.e., array[i] += array[i - 1];
        /// </summary>
        /// <param name="array">The array to accumulate</param>
        private void Accumulate(double[] array)
        {
            for (int i = 1; i < array.Length; i++)
            {
                array[i] += array[i - 1];
            }
        }

        /// <summary>
        /// Classification method for a data point
        /// </summary>
        /// <param name="incoming">An incoming datapoint, to be classified</param>
        /// <param name="K">The number of neighbors to use when classifying</param>
        /// <returns>The label(s) of the majority elements of the K nearest neighbors by rank</returns>
        public int[] Classify(List<object> incoming, int K)
        {

            // For each incoming data point
            for (int i = 0; i < incoming.Count; i++)
            {
                var column = _data[i];
                var columnIndex = _originalIndexes[i];
                var dp = incoming[i];
                var distance = _distances[i];
                var delta = _deltas[i];

                // What two elements are closest to the data point in the sorted data?
                int[] closest = BinarySearch(column, dp);

                // Check boundary cases first
                if (closest[0] < 0)
                {
                    // The closest data points are indexed at -1, 0. In this case the data is already sorted,
                    // with respect to the incoming data point so we only have to calculate the accumulated distances
                    // from the incoming data point
                    double[] incomingDistance = new double[column.Length];
                    incomingDistance[0] = distance(dp, column[0]);
                    Array.Copy(delta, 1, incomingDistance, 1, delta.Length - 1);
                    Accumulate(incomingDistance);
                    UpdateRankings(i, columnIndex, incomingDistance);
                }
                else if (closest[1] == column.Length)
                {
                    // The closest data points are indexed at length - 1, length. In this case the data are
                    // already sorted with respect to the incoming data point but in reverse order,
                    // so we have to reverse the deltas and then calculate the aggregate distance from the incoming data point
                    double[] incomingDistance = new double[column.Length];
                    Array.Copy(delta, incomingDistance, incomingDistance.Length);
                    Array.Reverse(incomingDistance, 1, incomingDistance.Length - 1); // First entry is zero so ignored
                    incomingDistance[0] = distance(dp, column[column.Length - 1]);
                    Accumulate(incomingDistance);
                    Array.Reverse(columnIndex);

                    // Calculate the rankings for this column
                    UpdateRankings(i, columnIndex, incomingDistance);

                    // Reverse the columnIndex back to where it was again
                    Array.Reverse(columnIndex);
                }
                else
                {
                    // The closest data points are indexed at n, n + 1 - non boundary case and we need
                    // to merge the data on either side of the incoming data point. The lower half of the
                    // data (array1) will be in reverse order
                    var array1 = new double[closest[0] + 1];
                    var index1 = new int[closest[0] + 1];
                    var array2 = new double[column.Length - closest[1]];
                    var index2 = new int[column.Length - closest[1]];

                    double d1 = distance(dp, column[closest[0]]);
                    double d2 = distance(dp, column[closest[1]]);

                    Array.Copy(delta, array1, array1.Length);
                    Array.Copy(columnIndex, index1, index1.Length);
                    Array.Reverse(array1, 1, array1.Length - 1); // First entry is zero so ignored
                    Array.Reverse(index1);
                    array1[0] = d1;
                    Accumulate(array1);

                    Array.Copy(delta, closest[1], array2, 0, array2.Length);
                    Array.Copy(columnIndex, closest[1], index2, 0, index2.Length);
                    array2[0] = d2;
                    Accumulate(array2);

                    double[] mergedDistance;
                    int[] mergedIndex;

                    var arrays = new List<double[]>();
                    arrays.Add(array1);
                    arrays.Add(array2);
                    var indexes = new List<int[]>();
                    indexes.Add(index1);
                    indexes.Add(index2);
                    MergeSorted(arrays, indexes, out mergedDistance, out mergedIndex);
                    UpdateRankings(i, mergedIndex, mergedDistance);
                }
            }
            // Get an aggregate ranking for each data point
            var aggregateRank = new double[_labels.Length];
            for (int j = 0; j < aggregateRank.Length; j++)
            {
                double[] ranks = new double[incoming.Count];

                for (int i = 0; i < ranks.Length; i++)
                {
                    ranks[i] = _rankings[i, j];
                }

                aggregateRank[j] = (_aggregator == null) ? ranks.Average() : _aggregator(ranks);
            }

            // Sort the aggregateRank and get out a permutation index
            var permidx = Enumerable.Range(0, aggregateRank.Length).ToArray();
            Array.Sort(aggregateRank, permidx);

            // Extract the k nearest neighbors using the permutation index
            var knn = new int[K];
            for (int k = 0; k < K; k++)
            {
                knn[k] = _labels[permidx[k]];
            }

            // And return the majority label(s) of the k nearest neighbors
            return Majority(knn);
        }

        /// <summary>
        /// Updates rankings for a column based on the supplied accumulated distances
        /// </summary>
        /// <param name="col">The column of the rankings to update</param>
        /// <param name="index">The original indexes of the relevant column for the sorted data</param>
        /// <param name="distance">The accumulated distances between data points</param>
        private void UpdateRankings(int col, int[] index, double[] distance)
        {
            // Figure out the ranking using the permutation index. 0 is the top rank
            int rank = 0;
            _rankings[col, index[0]] = rank;
            for (int j = 1; j < distance.Length; j++)
            {
                // Check that distance is greater than previous - if not we have an equal ranking
                if (distance[j] > distance[j - 1])
                {
                    rank++;
                }
                _rankings[col, index[j]] = rank;
            }
        }

        /// <summary>
        /// Returns the majority element(s) of an integer array. If there is a tie, multiple items are returned.
        /// </summary>
        /// <param name="array">The array to be searched</param>
        /// <returns>The majority</returns>
        private int[] Majority(int[] array)
        {
            var counts = new Dictionary<int, int>();

            for (int i = 0; i < array.Length; i++)
            {
                int count;
                if (counts.TryGetValue(array[i], out count))
                {
                    counts[array[i]] = count + 1;
                }
                else
                {
                    counts[array[i]] = 1;
                }
            }

            int maxCount = counts.Values.Max();

            var majorities = new List<int>();
            foreach (var count in counts)
            {
                if (count.Value == maxCount)
                {
                    majorities.Add(count.Key);
                }
            }

            return majorities.ToArray();
        }

        /// <summary>
        /// Finds the two indexes of that span x in the sorted array.
        /// If we get an exact match, we return the n, n+1 indexes of the match.
        /// </summary>
        /// <param name="sortedArray">An array of sorted data</param>
        /// <param name="x">The item to look for</param>
        /// <returns>An array containing two indexes that span the item</returns>
        private int[] BinarySearch(object[] sortedArray, object x)
        {
            int idx = Array.BinarySearch(sortedArray, x);
            if (idx < 0)
            {
                // If the bitwise complement is greater than the last index, it means x is greater than any array element.
                // Otherwise idx is specified as the bitwise complement of the first element larger than x.
                idx = ~idx;
                if (idx == sortedArray.Length)
                {
                    return new int[] { sortedArray.Length - 1, sortedArray.Length };
                }
                else
                {
                    return new int[] { idx - 1, idx };
                }
            }
            else
            {
                return new int[] { idx, idx + 1 };
            }
        }
    }
}
